package Algorithm.array;

/**
 * @Desc:   440. 字典序的第K小数字
 *          给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。
 *
 *          注意：1 ≤ k ≤ n ≤ 109。
 *
 *          示例 :
 *
 *          输入:
 *          n: 13   k: 2
 *
 *          输出:
 *          10
 *
 *          解释:
 *          字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
 *
 *
 * @author: cww
 * @DateTime: 2020-05-29 22:29
 */

public class FindKthNumber {
    public static int findKthNumber(int n, int k) {
        int curr = 1;
        k = k - 1;
        while (k > 0) {
            long steps = 0, first = curr, last = curr + 1;
            while (first <= n) {
                steps += Math.min((long)n + 1, last) - first;
                first *= 10;
                last *= 10;
            }
            if (steps <= k) {
                curr += 1;
                k -= steps;
            } else {
                curr *= 10;
                k -= 1;
            }
        }
        return curr;
    }

    public static void main(String[] args) {

//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        int k = sc.nextInt();
        System.out.println(findKthNumber(13,3));

    }
}
